7.3 מיון-מהיר (המשך) - חלוקה במקום

מבנה נתונים ואלגוריתמים

 

רוב היישומים של מיון-מהיר (quick sort) מנצלים את העובדה שניתן לבצע חלוקה במקום על ידי החזקת שני מצביעים: אחד הנכנס מצד שמאל והשני הנכנס מצד ימין. מצביעים אלו נעים לכיוון המרכז עד אשר המצביע השמאלי מוצא פריט הגדול מפריט הציר והימני מוצא פריט הקטן מפריט הציר. שני פריטים אלה מוחלפים אחד בשני. המצביעים ממשיכים להתקדם פנימה גם לאחר ההחלפה עד אשר הם חולפים זה על פניו של זה, ובמצב זה, מוחלף פריט הציר ומוכנס אל המקום שאליו מצביע המצביע הימני. בכך מסתיימת החלוקה.

<TBODY> int partition( void *a, int low, int high )   {   int left, right;   void *pivot_item;   pivot_item = a[low];   pivot = left = low;   right = high;   while ( left < right ) {     /* Move left while item < pivot */     while( a[left] <= pivot_item ) left++;     /* Move right while item > pivot */     while( a[right] > pivot_item ) right--;     if ( left < right ) SWAP(a,left,right);     }  /* right is final position for the pivot */   a[low] = a[right];   a[right] = pivot_item;   return right;   }

</TBODY>

<SMALL></SMALL>

יש לשים לב שהקוד אינו כולל בדיקה כי left אינו חורג מתחום המערך. יש צורך להוסיף בדיקה זו לפני ביצוע ההחלפות - הן זו שבלולאה והן זו שמחוץ ללולאה.

 

הפונקציה partition מבטיחה שכל הפריטים הקטנים מפריט הציר יקדמו לו, ומחזירה את מיקומו של פריט הציר. זה תואם את התנאי שלנו לחלוקת הבעיה: כל הפריטים בחלק התחתון הם קטנים מפריט הציר וכל הפריטים בחלק העליון גדולים ממנו.

 

שים לב כי אנו משתמשים בפונקציה ItemCmp בתוך הפונקציה partition. הדבר נובע מההנחות כי קיימת הצהרה חיצונית עבור ItemCmp וכי בכל תוכנית אנו רוצים למיין רק סוג אחד של אובייקטים. לרוב דבר זה אינו קביל, ולכן ההגדרות הפורמליות של מיון-מהיר בספריות Unix ו- ANSI C כוללות את פונקצית compar המסייעת ל-qsort כאשר זו נקראת. הפונקציה compar, המגדירה את סידור האובייקטים כאשר קוראים ל- qsort, מונעת את הבעיה באותו אופן כפי שקורה כשאנו מעבירים את פונקצית ItemCmp ל- ConsCollection.

 

 

ניתוח

השגרה partition בוחנת כל פריט במערך פעם אחת לכל היותר, ולכן היא בבירור O(n). בדרך כלל שגרה זו תחלק את הבעיה לשני חלקים אשר באופן כללי די שווים בגודלם. אנו יודעים

כי ניתן לחלק n פריטים לחציlog₂n  פעמים. זה הופך את מיון-מהיר לאלגוריתם של O(nlogn)

- בדומה למיון ערמה.

 

אולם, הנחנו הנחה בלתי מוצדקת! - נסה לגלותה בעצמך לפני שנמשיך.

 

 

 

מושגים

 

אלגוריתם מסוג "הפרד ומשול"

אלגוריתם הפותר בעיות (מושל) על ידי חלוקתן לתת-בעיות קטנות יותר שוב ושוב, עד שהבעיות כה קטנות שפתרונן טריוויאלי.

 

 

המשך ל: מיון מהיר - המשך                     חזור ל: תוכן עניינים